import string

from stack import Stack


def infix_to_postfix(expr):
    prec = {}
    prec['*'] = 3
    prec['/'] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec['('] = 1

    op_stack = Stack()
    post_fix_list = []

    token_list = expr.split()

    for token in token_list:

        # 如果是字母则将其放入结果列表
        if token in string.ascii_uppercase:
            post_fix_list.append(token)

        # 如果是左括号就将其压入栈中
        elif token == '(':
            op_stack.push(token)

        # 当出现右括号时，将栈底pop出来，如果是操作数就将其追到到结果列表末尾，如果是左括号则结束循环（即使是左括号，也被pop出来，保证了左右括号的消除）
        elif token == ')':
            top_token = op_stack.pop()
            while top_token != '(':
                post_fix_list.append(top_token)
                top_token = op_stack.pop()

        # 如果是操作数
        else:
            while not op_stack.is_empty() and prec[op_stack.peek()] >= prec[token]:
                post_fix_list.append(op_stack.pop())
            op_stack.push(token)

    while not op_stack.is_empty():
        post_fix_list.append(op_stack.pop())

    return ''.join(post_fix_list)


def practice(expr):

    prec = {}
    prec['*'] = 3
    prec['/'] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec['('] = 1

    s = Stack()
    result_list = []

    expr_list = expr.split()

    for token in expr_list:
        if token in string.ascii_uppercase:
            result_list.append(token)

        elif token == '(':
            s.push(token)

        elif token == ')':
            top_token = s.pop()
            while top_token != '(':
                result_list.append(top_token)
                top_token = s.pop()

        else:
            while not s.is_empty() and prec[s.peek()] >= prec[token]:
                result_list.append(s.pop())

            s.push(token)
    while not s.is_empty():
        result_list.append(s.pop())

    return ''.join(result_list)


if __name__ == '__main__':
    s = ' ( A + B ) * ( C + D ) '
    print(practice(s))